/*
 * @Author: your name
 * @Date: 2020-09-08 16:54:43
 * @LastEditTime: 2020-09-09 09:48:13
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /InsertionSort/InsertionSort.cpp
 */
#include <iostream>

using namespace std;

//直接插入法1
void InsertionSort(int arry[])
{
    //int len=(sizeof(arry)/sizeof(arry[0]));  //定义数组长度
    for(int i=0; i<5; i++)
	{        
        int temp = arry[i+1];
	    int j = i;
	    while(j > -1 && temp < arry[j])
	    {        
            arry[j+1] = arry[j];
		    j--;
	    }
	    arry[j+1] = temp;
	}         
}

// //优化：二叉搜索
// int search(int arry[],int v)
// {
//     int len=(sizeof(arry)/sizeof(arry[0]));  //定义数组长度
//     if(arry==NULL || len==0)
//         return -1;
//     int begin=0;
//     int end=len;
//     while (begin<end)
//     {
//         int mid=(begin+end)/2;
//         if(v<arry[mid])
//             end=mid;
//         else if(v>arry[mid])
//             begin=mid+1;
//         else
//             return mid;
//     }
//     return -1;
    
// }

//二分查找
//index为找到index位置元素待插入位置
int Search(int arry[],int index)
{
    //int len=(sizeof(arry)/sizeof(arry[0]));  //定义数组长度
    int len=6;
    int begin=0;
    int end=len;
    if(arry==NULL || len==0)
        return -1;
    while (begin<end)
    {
        //int mid=(begin+end)/2;
        int mid=(begin+end)>>1;
        if(arry[index]<arry[mid])
            end=mid;
        else
            begin=mid+1;
    }
    return begin;
}

void InsertionSort2(int arry[])
{
    int len=6;
    for (int begin = 1; begin<len; begin++)
    {
        int v=arry[begin];
        int insertIndex=Search(arry,begin);
        for (int i = begin; i>insertIndex; i--)
        {
            arry[i]=arry[i-1];
        }
        arry[insertIndex]=v;
    }
}

int main()
{
    int arry[6]={30,17,89,67,45,59};
    //InsertionSort(arry);
    InsertionSort2(arry);
    for (int i = 0; i <6; i++)
    {
        cout<<arry[i]<<" ";
    }
    cout<<endl;
    return 0;
}